算法 - 栈和队列.md

算法 - 栈和队列

• 算法 - 栈和队列
  • 栈
    • 1. 数组实现
    • 2. 链表实现
  • 队列

栈

publicinterfaceMyStack<Item> extendsIterable<Item> { MyStack<Item> push(Itemitem); Itempop() throwsException; booleanisEmpty(); intsize(); }

1. 数组实现

publicclassArrayStack<Item> implementsMyStack<Item> { // 栈元素数组，只能通过转型来创建泛型数组privateItem[] a = (Item[]) newObject[1]; // 元素数量privateintN = 0; @OverridepublicMyStack<Item> push(Itemitem) { check(); a[N++] = item; returnthis; } @OverridepublicItempop() throwsException { if (isEmpty()) { thrownewException("stack is empty"); } Itemitem = a[--N]; check(); // 避免对象游离a[N] = null; returnitem; } privatevoidcheck() { if (N >= a.length) { resize(2 * a.length); } elseif (N > 0 && N <= a.length / 4) { resize(a.length / 2); } } /** * 调整数组大小，使得栈具有伸缩性 */privatevoidresize(intsize) { Item[] tmp = (Item[]) newObject[size]; for (inti = 0; i < N; i++) { tmp[i] = a[i]; } a = tmp; } @OverridepublicbooleanisEmpty() { returnN == 0; } @Overridepublicintsize() { returnN; } @OverridepublicIterator<Item> iterator() { // 返回逆序遍历的迭代器returnnewIterator<Item>() { privateinti = N; @OverridepublicbooleanhasNext() { returni > 0; } @OverridepublicItemnext() { returna[--i]; } }; } }

2. 链表实现

需要使用链表的头插法来实现，因为头插法中最后压入栈的元素在链表的开头，它的 next 指针指向前一个压入栈的元素，在弹出元素时就可以通过 next 指针遍历到前一个压入栈的元素从而让这个元素成为新的栈顶元素。

publicclassListStack<Item> implementsMyStack<Item> { privateNodetop = null; privateintN = 0; privateclassNode { Itemitem; Nodenext; } @OverridepublicMyStack<Item> push(Itemitem) { NodenewTop = newNode(); newTop.item = item; newTop.next = top; top = newTop; N++; returnthis; } @OverridepublicItempop() throwsException { if (isEmpty()) { thrownewException("stack is empty"); } Itemitem = top.item; top = top.next; N--; returnitem; } @OverridepublicbooleanisEmpty() { returnN == 0; } @Overridepublicintsize() { returnN; } @OverridepublicIterator<Item> iterator() { returnnewIterator<Item>() { privateNodecur = top; @OverridepublicbooleanhasNext() { returncur != null; } @OverridepublicItemnext() { Itemitem = cur.item; cur = cur.next; returnitem; } }; } }

队列

下面是队列的链表实现，需要维护 first 和 last 节点指针，分别指向队首和队尾。

这里需要考虑 first 和 last 指针哪个作为链表的开头。因为出队列操作需要让队首元素的下一个元素成为队首，所以需要容易获取下一个元素，而链表的头部节点的 next 指针指向下一个元素，因此可以让 first 指针链表的开头。

publicinterfaceMyQueue<Item> extendsIterable<Item> { intsize(); booleanisEmpty(); MyQueue<Item> add(Itemitem); Itemremove() throwsException; }

publicclassListQueue<Item> implementsMyQueue<Item> { privateNodefirst; privateNodelast; intN = 0; privateclassNode { Itemitem; Nodenext; } @OverridepublicbooleanisEmpty() { returnN == 0; } @Overridepublicintsize() { returnN; } @OverridepublicMyQueue<Item> add(Itemitem) { NodenewNode = newNode(); newNode.item = item; newNode.next = null; if (isEmpty()) { last = newNode; first = newNode; } else { last.next = newNode; last = newNode; } N++; returnthis; } @OverridepublicItemremove() throwsException { if (isEmpty()) { thrownewException("queue is empty"); } Nodenode = first; first = first.next; N--; if (isEmpty()) { last = null; } returnnode.item; } @OverridepublicIterator<Item> iterator() { returnnewIterator<Item>() { Nodecur = first; @OverridepublicbooleanhasNext() { returncur != null; } @OverridepublicItemnext() { Itemitem = cur.item; cur = cur.next; returnitem; } }; } }